home *** CD-ROM | disk | FTP | other *** search
/ CU Amiga Super CD-ROM 25 / CU Amiga Magazine's Super CD-ROM 25 (1998)(EMAP Images)(GB)(Track 1 of 2)[!][issue 1998-08].iso / CUCD / Programming / QuakeTools / src / libqbuild / tjunc.c < prev    next >
Encoding:
C/C++ Source or Header  |  1998-06-11  |  10.8 KB  |  487 lines
  1. #define    LIBQBUILD_CORE
  2. #include "../include/libqbuild.h"
  3.  
  4. #define    NUM_HASH    1024
  5.  
  6. struct wvert {
  7.   vec_t t;
  8.   struct wvert *prev, *next;
  9. } __packed;    // 12
  10.  
  11. struct wedge {
  12.   struct wedge *next;
  13.   vec3_t dir;
  14.   vec3_t origin;
  15.   struct wvert head;
  16. } __packed;    // 40
  17.  
  18. int numwedges, numwverts;                    // 8
  19. int tjuncs;                            // 4
  20. int tjuncfaces;                            // 4
  21.  
  22. /* changed by niels */
  23. struct wvert *wverts = 0;
  24. struct wedge *wedges = 0;
  25. struct wedge *wedge_hash[NUM_HASH];                // 4096
  26. vec3_t hash_min, hash_scale;                    // 24
  27.  
  28. // a specially allocated face that can hold hundreds of edges if needed
  29. //byte superfacebuf[8192];                        // 8192
  30. //struct visfacet *superface = (struct visfacet *) superfacebuf;    // 4
  31. struct visfacet *superface;
  32. struct visfacet *newlist;                    // 4
  33. /* PROGRESS-ONLY! */
  34. int tjuncnum;
  35. int tjunccur;
  36.  
  37. //============================================================================
  38.  
  39. void PrintFace(register struct visfacet * f)
  40. {
  41.   int i;
  42.  
  43.   for (i = 0; i < f->numpoints; i++)
  44.     mprintf("( %g %g %g )\n", f->pts[i][0], f->pts[i][1], f->pts[i][2]);
  45. }
  46.  
  47. void InitTJHash(register vec3_t mins, register vec3_t maxs)
  48. {
  49.   vec3_t size;
  50.   vec_t volume;
  51.   vec_t scale;
  52.   int newsize[2];
  53.  
  54.   VectorCopy(mins, hash_min);
  55.   VectorSubtract(maxs, mins, size);
  56.   memset(wedge_hash, 0, sizeof(wedge_hash));
  57.  
  58.   volume = size[0] * size[1];
  59.  
  60.   scale = sqrt(volume / NUM_HASH);
  61.  
  62.   newsize[0] = size[0] / scale;
  63.   newsize[1] = size[1] / scale;
  64.  
  65.   hash_scale[0] = newsize[0] / size[0];
  66.   hash_scale[1] = newsize[1] / size[1];
  67.   hash_scale[2] = newsize[1];
  68. }
  69.  
  70. unsigned TJHashVec(register vec3_t vec)
  71. {
  72.   unsigned h;
  73.  
  74.   h = hash_scale[0] * (vec[0] - hash_min[0]) * hash_scale[2]
  75.     + hash_scale[1] * (vec[1] - hash_min[1]);
  76.   if (h >= NUM_HASH)
  77.     return NUM_HASH - 1;
  78.   return h;
  79. }
  80.  
  81. //============================================================================
  82.  
  83. void CanonicalVector(register vec3_t vec)
  84. {
  85.   VectorNormalize(vec);
  86.   if (vec[0] > EQUAL_EPSILON)
  87.     return;
  88.   else if (vec[0] < -EQUAL_EPSILON) {
  89.     VectorNegate(vec);
  90.     return;
  91.   }
  92.   else
  93.     vec[0] = 0;
  94.  
  95.   if (vec[1] > EQUAL_EPSILON)
  96.     return;
  97.   else if (vec[1] < -EQUAL_EPSILON) {
  98.     VectorNegate(vec);
  99.     return;
  100.   }
  101.   else
  102.     vec[1] = 0;
  103.  
  104.   if (vec[2] > EQUAL_EPSILON)
  105.     return;
  106.   else if (vec[2] < -EQUAL_EPSILON) {
  107.     VectorNegate(vec);
  108.     return;
  109.   }
  110.   else
  111.     vec[2] = 0;
  112.   Error("CanonicalVector: degenerate");
  113. }
  114.  
  115. struct wedge *FindEdge(register vec3_t p1, register vec3_t p2, register vec_t * t1, register vec_t * t2)
  116. {
  117.   vec3_t origin;
  118.   vec3_t dir;
  119.   struct wedge *w;
  120.   vec_t temp;
  121.   int h;
  122.  
  123.   VectorSubtract(p2, p1, dir);
  124.   CanonicalVector(dir);
  125.  
  126.   *t1 = DotProduct(p1, dir);
  127.   *t2 = DotProduct(p2, dir);
  128.  
  129.   VectorMA(p1, -*t1, dir, origin);
  130.  
  131.   if (*t1 > *t2) {
  132.     temp = *t1;
  133.     *t1 = *t2;
  134.     *t2 = temp;
  135.   }
  136.  
  137.   h = TJHashVec(origin);
  138.  
  139.   for (w = wedge_hash[h]; w; w = w->next) {
  140.     temp = w->origin[0] - origin[0];
  141.     if (temp < -EQUAL_EPSILON || temp > EQUAL_EPSILON)
  142.       continue;
  143.     temp = w->origin[1] - origin[1];
  144.     if (temp < -EQUAL_EPSILON || temp > EQUAL_EPSILON)
  145.       continue;
  146.     temp = w->origin[2] - origin[2];
  147.     if (temp < -EQUAL_EPSILON || temp > EQUAL_EPSILON)
  148.       continue;
  149.  
  150.     temp = w->dir[0] - dir[0];
  151.     if (temp < -EQUAL_EPSILON || temp > EQUAL_EPSILON)
  152.       continue;
  153.     temp = w->dir[1] - dir[1];
  154.     if (temp < -EQUAL_EPSILON || temp > EQUAL_EPSILON)
  155.       continue;
  156.     temp = w->dir[2] - dir[2];
  157.     if (temp < -EQUAL_EPSILON || temp > EQUAL_EPSILON)
  158.       continue;
  159.  
  160.     return w;
  161.   }
  162.  
  163.   /* changed by Niels */
  164.   if(!(w = (struct wedge *)kmalloc(sizeof(struct wedge))))
  165.     Error("FindEdge: failed to allocate wedge!\n");
  166.   numwedges++;
  167.  
  168.   w->next = wedge_hash[h];
  169.   wedge_hash[h] = w;
  170.  
  171.   VectorCopy(origin, w->origin);
  172.   VectorCopy(dir, w->dir);
  173.   w->head.next = w->head.prev = &w->head;
  174.   w->head.t = 99999;
  175.   return w;
  176. }
  177.  
  178. /*
  179.  * ===============
  180.  * AddVert
  181.  * 
  182.  * ===============
  183.  */
  184.  
  185. void AddVert(register struct wedge * w, register vec_t t)
  186. {
  187.   struct wvert *v, *newv;
  188.  
  189.   v = w->head.next;
  190.   do {
  191.     if (fabs(v->t - t) < T_EPSILON)
  192.       return;
  193.     if (v->t > t)
  194.       break;
  195.     v = v->next;
  196.   } while (1);
  197.  
  198. // insert a new wvert before v
  199.   /* changed by niels */
  200.   if(!(newv = (struct wvert *)kmalloc(sizeof(struct wvert))))
  201.     Error("AddVert: failed to allocate newv!\n");
  202.   numwverts++;
  203.  
  204.   newv->t = t;
  205.   newv->next = v;
  206.   newv->prev = v->prev;
  207.   v->prev->next = newv;
  208.   v->prev = newv;
  209. }
  210.  
  211. /*
  212.  * ===============
  213.  * AddEdge
  214.  * 
  215.  * ===============
  216.  */
  217. void AddEdge(register vec3_t p1, register vec3_t p2)
  218. {
  219.   struct wedge *w;
  220.   vec_t t1, t2;
  221.  
  222.   w = FindEdge(p1, p2, &t1, &t2);
  223.   AddVert(w, t1);
  224.   AddVert(w, t2);
  225. }
  226.  
  227. /*
  228.  * ===============
  229.  * AddFaceEdges
  230.  * 
  231.  * ===============
  232.  */
  233. void AddFaceEdges(register struct visfacet * f)
  234. {
  235.   int i, j;
  236.  
  237.   for (i = 0; i < f->numpoints; i++) {
  238.     j = (i + 1) % f->numpoints;
  239.     AddEdge(f->pts[i], f->pts[j]);
  240.   }
  241. }
  242.  
  243. //============================================================================
  244.  
  245. void SplitFaceForTjunc(register struct visfacet * f, register struct visfacet * original)
  246. {
  247.   int i;
  248.   struct visfacet *new, *chain;
  249.   vec3_t dir, test;
  250.   vec_t v;
  251.   int firstcorner, lastcorner;
  252.  
  253.   chain = NULL;
  254.   do {
  255.     if (f->numpoints <= MAXPOINTS) {                           // the face is now small enough without more cutting
  256.       // so copy it back to the original
  257.       CopyFace(original, f);
  258.       original->original = chain;
  259.       original->next = newlist;
  260.       newlist = original;
  261.       return;
  262.     }
  263.  
  264.     tjuncfaces++;
  265.  
  266.   restart:
  267.     // find the last corner 
  268.     VectorSubtract(f->pts[f->numpoints - 1], f->pts[0], dir);
  269.     VectorNormalize(dir);
  270.     for (lastcorner = f->numpoints - 1; lastcorner > 0; lastcorner--) {
  271.       VectorSubtract(f->pts[lastcorner - 1], f->pts[lastcorner], test);
  272.       VectorNormalize(test);
  273.       v = DotProduct(test, dir);
  274.       if (v < 0.9999 || v > 1.00001) {
  275.     break;
  276.       }
  277.     }
  278.  
  279.     // find the first corner        
  280.     VectorSubtract(f->pts[1], f->pts[0], dir);
  281.     VectorNormalize(dir);
  282.     for (firstcorner = 1; firstcorner < f->numpoints - 1; firstcorner++) {
  283.       VectorSubtract(f->pts[firstcorner + 1], f->pts[firstcorner], test);
  284.       VectorNormalize(test);
  285.       v = DotProduct(test, dir);
  286.       if (v < 0.9999 || v > 1.00001) {
  287.     break;
  288.       }
  289.     }
  290.  
  291.     if (firstcorner + 2 >= MAXPOINTS) {
  292.       // rotate the point winding
  293.       VectorCopy(f->pts[0], test);
  294.       //memcpy(f->pts + 1, f->pts, (f->numpoints - 1) * sizeof(vec3_t));
  295.       for (i = 1; i < f->numpoints; i++) {
  296.     VectorCopy(f->pts[i], f->pts[i - 1]);
  297.       }
  298.       VectorCopy(test, f->pts[f->numpoints - 1]);
  299.       goto restart;
  300.     }
  301.  
  302.     // cut off as big a piece as possible, less than MAXPOINTS, and not
  303.     // past lastcorner
  304.  
  305.     new = NewFaceFromFace(f, MAXPOINTS);
  306.     if (f->original)
  307.       Error("SplitFaceForTjunc: f->original");
  308.  
  309.     new->original = chain;
  310.     chain = new;
  311.     new->next = newlist;
  312.     newlist = new;
  313.     if (f->numpoints - firstcorner <= MAXPOINTS)
  314.       new->numpoints = firstcorner + 2;
  315.     else if (lastcorner + 2 < MAXPOINTS &&
  316.          f->numpoints - lastcorner <= MAXPOINTS)
  317.       new->numpoints = lastcorner + 2;
  318.     else
  319.       new->numpoints = MAXPOINTS;
  320.  
  321.     //memcpy(new->pts, f->pts, new->numpoints * sizeof(vec3_t));
  322.     for (i = 0; i < new->numpoints; i++) {
  323.       VectorCopy(f->pts[i], new->pts[i]);
  324.     }
  325.  
  326.     //memcpy(f->pts, f->pts + new->numpoints - 1, (f->numpoints - (new->numpoints - 2)) * sizeof(vec3_t));
  327.     for (i = new->numpoints - 1; i < f->numpoints; i++) {
  328.       VectorCopy(f->pts[i], f->pts[i - (new->numpoints - 2)]);
  329.     }
  330.     f->numpoints -= (new->numpoints - 2);
  331.  
  332.     RecalcFace(f);
  333.     RecalcFace(new);
  334.   } while (1);
  335. }
  336.  
  337. /*
  338.  * ===============
  339.  * FixFaceEdges
  340.  * 
  341.  * ===============
  342.  */
  343. void FixFaceEdges(register struct visfacet * f)
  344. {
  345.   int i, j, k;
  346.   struct wedge *w;
  347.   struct wvert *v;
  348.   vec_t t1, t2;
  349.  
  350.   /* allocate the mega-face */
  351.   superface = AllocFace(1024);                                /* 512 faces: 34 + 1024*12 + 1024*4 = 8226*2 */
  352.   memcpy(superface, f, sizeof(struct visfacet) - sizeof(vec3_t *) - sizeof(int *));    /* <- small hack to not overwrite the allocated pts/edges */
  353.   memcpy(superface->pts, f->pts, f->numpoints * sizeof(vec3_t));
  354.   memcpy(superface->edges, f->edges, f->numpoints * sizeof(int));
  355.  
  356. restart:
  357.   for (i = 0; i < superface->numpoints; i++) {
  358.     j = (i + 1) % superface->numpoints;
  359.  
  360.     w = FindEdge(superface->pts[i], superface->pts[j], &t1, &t2);
  361.  
  362.     for (v = w->head.next; v->t < t1 + T_EPSILON; v = v->next) {
  363.     }
  364.  
  365.     if (v->t < t2 - T_EPSILON) {
  366.       tjuncs++;
  367.       // insert a new vertex here
  368.       //memcpy(superface->pts + j + 1, superface->pts + j, superface->numpoints - j);
  369.       //for (k = j; k < superface->numpoints; k++) {
  370.       //  VectorCopy(superface->pts[k], superface->pts[k + 1]);
  371.       //}
  372.       for (k = superface->numpoints; k > j; k--) {
  373.     VectorCopy(superface->pts[k - 1], superface->pts[k]);
  374.       }
  375.       VectorMA(w->origin, v->t, w->dir, superface->pts[j]);
  376.       superface->numpoints++;
  377.       goto restart;
  378.     }
  379.   }
  380.  
  381.   if (superface->numpoints <= MAXPOINTS) {
  382.     CopyFace(f, superface);
  383.     FreeFace(superface);
  384.     f->next = newlist;
  385.     newlist = f;
  386.     return;
  387.   }
  388.  
  389. // the face needs to be split into multiple faces because of too many edges
  390.  
  391.   SplitFaceForTjunc(superface, f);
  392.   FreeFace(superface);
  393. }
  394.  
  395. //============================================================================
  396.  
  397. void tjunc_find_r(register struct node * node)
  398. {
  399.   struct visfacet *f;
  400.   
  401.   /* PROGRESS-ONLY! */
  402.   tjuncnum++;
  403.  
  404.   if (node->planenum == PLANENUM_LEAF)
  405.     return;
  406.  
  407.   for (f = node->faces; f; f = f->next)
  408.     AddFaceEdges(f);
  409.  
  410.   tjunc_find_r(node->children[0]);
  411.   tjunc_find_r(node->children[1]);
  412. }
  413.  
  414. void tjunc_fix_r(register struct node * node)
  415. {
  416.   struct visfacet *f, *next;
  417.   
  418.   /* PROGRESS-ONLY! */
  419.   mprogress(tjuncnum, ++tjunccur);
  420.  
  421.   if (node->planenum == PLANENUM_LEAF)
  422.     return;
  423.  
  424.   newlist = NULL;
  425.  
  426.   for (f = node->faces; f; f = next) {
  427.     next = f->next;
  428.     FixFaceEdges(f);
  429.   }
  430.  
  431.   node->faces = newlist;
  432.  
  433.   tjunc_fix_r(node->children[0]);
  434.   tjunc_fix_r(node->children[1]);
  435. }
  436.  
  437. /*
  438.  * ===========
  439.  * tjunc
  440.  * 
  441.  * ===========
  442.  */
  443. void tjunc(struct node * headnode)
  444. {
  445.   vec3_t maxs, mins;
  446.   short int i;
  447.  
  448.   mprintf("----- tjunc ------------\n");
  449.   /* PROGRESS-ONLY! */
  450.   tjuncnum = 0;
  451.   tjunccur = 0;
  452.  
  453.   /*
  454.    * identify all points on common edges
  455.    */
  456.  
  457.   // origin points won't allways be inside the map, so extend the hash area 
  458.   for (i = 0; i < 3; i++) {
  459.     if (fabs(brushset->maxs[i]) > fabs(brushset->mins[i]))
  460.       maxs[i] = fabs(brushset->maxs[i]);
  461.     else
  462.       maxs[i] = fabs(brushset->mins[i]);
  463.   }
  464.   VectorNegateTo(maxs, mins);
  465.  
  466.   InitTJHash(mins, maxs);
  467.  
  468.   numwedges = numwverts = 0;
  469.  
  470.   tjunc_find_r(headnode);
  471.  
  472.   mprintf("%5i world edges\n%5i edge points\n", numwedges, numwverts);
  473.  
  474.   /*
  475.    * add extra vertexes on edges where needed
  476.    */
  477.   tjuncs = tjuncfaces = 0;
  478.  
  479.   tjunc_fix_r(headnode);
  480.  
  481.   mprintf("%5i edges added by tjunctions\n", tjuncs);
  482.   mprintf("%5i faces added by tjunctions\n", tjuncfaces);
  483.   
  484.   /* added by niels */
  485.   kfree();
  486. }
  487.